#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

//杨氏矩阵
//有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，
//请编写程序在这样的矩阵中查找某个数字是否存在。
//要求：时间复杂度小于O(N);
int find_key(int arr[3][3], int* px, int* py, int k)
{
	//从右上角开始找
	int x = 0;
	int y = *py - 1;
	while (x < *px && y >= 0)
	{
		if (arr[x][y] < k)
		{
			x++;
		}
		else if (arr[x][y] > k)
		{
			y--;
		}
		else
		{
			//将找到元素的下标带回去
			*px = x;
			*py = y;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int key = 7;
	int x = 3;//行数
	int y = 3;//列数
	int ret=find_key(arr,&x, &y, key);
	if (ret == 1)
	{
		printf("找到了,下标为\n");
		printf("%d,%d", x, y);
	}
	else
		printf("没找到\n");
	return 0;
}